A conventional approach to efficiently store information is deduplication. Deduplication removes the redundancy commonly found in all types of data. Examples of such redundancy include multiple copies of the same file in a storage device. By storing only a single instance of the file and using pointers to reference that single instance, deduplication helps to reduce the amount of storage capacity consumed by data.
The pointers are typically stored in an index. Unfortunately, if the index containing those pointers is lost or altered, all of the data pointed to becomes inaccessible. Further, if the index is large, it may require considerable resources to search through the index to find deduplicated data. There is a need, therefore, for an improved method, article of manufacture, and apparatus for storing information.